package leetcode;

/**
 * 描述:最长回文子串
 *
 * @author Madison You
 * @created 21:36
 */
public class Mid_5_LongestPalindrome {

    public static void main(String[] args) {
        System.out.println(longestPalindrome("babad"));
    }

    /*中心扩散法*/
    public static String longestPalindrome(String s) {
        int len = s.length();
        if (len <= 1) {
            return s;
        }
        int begin = 0;
        int maxlen = 0;
        char[] chars = s.toCharArray();
        for (int i = 1; i < len-1; i++) {
            int expand1 = expand(chars, i, i);
            int expand2 = expand(chars, i, i + 1);
            int max = Math.max(expand1, expand2);
            if (max > maxlen) {
                maxlen = max;
                begin = i - (maxlen - 1) / 2;
            }

        }
        return s.substring(begin, begin + maxlen);
    }

    private static int expand(char[] chars, int i, int j) {
        int len = chars.length;
        while (i > 0 & j < len) {
            if (chars[i] == chars[j]) {
                i--;
                j++;
            }else {
                break;
            }
        }
        return j - i - 1;
    }
}
